
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _SimpleListNode SimpleListNode;
typedef struct _SimpleSortList SimpleSortList;

struct _SimpleListNode {
    SimpleListNode* next;
    SimpleListNode* pre;
    void* val;
};

struct _SimpleSortList {
    SimpleListNode* first;
    int (*match)(void* cur_val, void* query_arg);
    int (*compare)(void* cur_val, void* inst_val);
    void (*free)(void* cur_val);
};

static inline SimpleListNode* new_node()
{
    SimpleListNode* node = (SimpleListNode*)malloc(sizeof(SimpleListNode));
    if (!node) {
        perror("malloc memory\n");
        abort();
    }
    memset(node, 0, sizeof(SimpleListNode));
    return node;
}

static inline void free_node(SimpleListNode* node)
{
    free(node);
}

void* find_val(SimpleSortList* list, void* query_arg)
{
    if (!list)
        return NULL;
    SimpleListNode* tnode = list->first;
    for (; tnode; tnode = tnode->next) {
        if (list->match(tnode->val, query_arg))
            return tnode->val;
    }
    return NULL;
}

SimpleListNode* find(SimpleSortList* list, void* query_arg)
{
    if (!list)
        return NULL;
    SimpleListNode* tnode = list->first;
    for (; tnode; tnode = tnode->next) {
        if (list->match(tnode->val, query_arg))
            return tnode;
    }
    return NULL;
}

// SimpleListNode* near_or_match(SimpleSortList* list, void* query_arg)
// {
//     if (!list)
//         return NULL;
//     SimpleListNode* tnode = list->first;
//     for (; tnode; tnode = tnode->next) {
//         if (list->near_match(tnode->val, query_arg))
//             return tnode;
//     }
//     return NULL;
// }

static void insert_after(SimpleSortList* list, SimpleListNode** pos_node, void* insert_val)
{
    assert(pos_node != NULL && list != NULL);
    SimpleListNode* las_pos = NULL;
    for (; *pos_node; pos_node = &(*pos_node)->next) {
        if (list->compare((*pos_node)->val, insert_val) > 0) {
            // 升序排列,插入到当前位置的前一个
            break;
        }
        las_pos = *pos_node;
    }
    SimpleListNode* node = new_node();
    node->val = insert_val;
    node->next = *pos_node;
    if (*pos_node) {
        node->pre = (*pos_node)->pre;
        (*pos_node)->pre = node;
    } else {
        node->pre = las_pos;
    }
    *pos_node = node;
}

static void insert_before(SimpleSortList* list, SimpleListNode** pos_node, void* insert_val)
{
    assert(pos_node != NULL && list != NULL);
    for (; *pos_node; pos_node = &(*pos_node)->pre) {
        if (list->compare((*pos_node)->val, insert_val) < 0) {
            // 升序排列,插入到当前位置的前一个
            break;
        }
    }
    SimpleListNode* node = new_node();
    node->val = insert_val;
    node->next = *pos_node;
    if (*pos_node) {
        node->pre = (*pos_node)->pre;
        (*pos_node)->pre = node;
    } else {
        node->pre = NULL;
    }
    *pos_node = node;
}

void insert_at(SimpleSortList* list, SimpleListNode* node, void* insert_val)
{
    assert(list != NULL);
    SimpleListNode** pos;
    if (node == list->first)
        pos = &(list->first);
    else
        pos = &(node->pre->next);

    // printf("v: %d, %d\n", *(int*)(node->val), *(int*)(node->pre->val));
    // printf("xxx: %p\n", (*pos));
    if (list->compare(node->val, insert_val) < 0)
        insert_after(list, pos, insert_val);
    else
        insert_before(list, pos, insert_val);
}

void insert(SimpleSortList* list, void* inster_val)
{
    assert(list != NULL);
    insert_after(list, &(list->first), inster_val);
}

void delete (SimpleSortList* list, SimpleListNode* node)
{
    if (list == NULL || node == NULL)
        return;
    SimpleListNode** pos_node = &(list->first);
    for (; *pos_node; pos_node = &(*pos_node)->next) {
        if (*pos_node == node) {
            *pos_node = node->next;
            if (node->next)
                node->next->pre = node->pre;
            list->free(node->val);
            free_node(node);
            break;
        }
    }
}

/**
 * 遍历所有节点,每个节点回调call, call返回1中止遍历
 **/
void foreach_list(SimpleSortList* list, int (*call)(void* cur_val, void* arg), void* arg)
{
    if (list == NULL)
        return;
    SimpleListNode* node = list->first;
    for (; node; node = node->next) {
        if (call(node->val, arg))
            break;
        // printf("pre: %p, next: %p\n", node->pre, node->next);
    }
}